package com.leetcode.剑指Offer;
	
/**
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
 */
/**
 * 仔细观察矩阵，可以发现：左下角元素为'所在列'最大元素，'所在行'最小元素

如果 左下角元素 大于了目标值，则目标值一定在'该行'的上方， 左下角元素 '所在行'可以消去。

如果 左下角元素 小于了目标值，则目标值一定在'该列'的右方， 左下角元素 '所在列'可以消去。

具体操作为从矩阵左下角元素开始遍历，并与目标值对比：

当 matrix[i][j] > target 时： 行索引向上移动一格（即 i--），即消去矩阵第 i 行元素；
当 matrix[i][j] < target 时： 列索引向右移动一格（即 j++），即消去矩阵第 j 列元素；
当 matrix[i][j] == target 时： 返回 true。
如果越界，则返回 false。
 *
 */
public class Offer04二维数组中的查找 {
	
	public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length - 1;
        int j = 0;
        while(i >= 0 && j < matrix[0].length){
            if(matrix[i][j] == target) return true;
            if(matrix[i][j] < target) j++;
            else i--;
        }
        return false;
    }
}
